package leetcode每日一题;


import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Stack;


/**
 * 1. 问题描述
 *      给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
 *      需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 *
 * 2. 算法分析
 *      分析题意：
 *          给定一个字符串，我们需要去除字符串中的重复字符，并且需要返回字典序最小的一个
 *          例如bab，我们需要删除第一个b保留ab，因为ab的字典序小于ba
 *
 *      具体例子：
 *          1. "bcabc"
 *              直观看上去，我们知道最小字典序字符串就是abc，但是这个结果我们是怎么得来的呢?
 *              由于需要最终结果保持每个字符的相对顺序不变，先一个一个字符遍历：
 *                  第一个字符为b，此时只出现了一次，所以保留，第二个字符为c，只出现了一次，
 *                  并且保持字典序，保留，当遍历到第三个字符a时，我们发现之前的字典序破坏了
 *                  所以此时我们需要判断a之后是否出现了c，如果出现了，删除c，接着判断b是否在
 *                  a之后也出现了，由上述给的字符串发现，此时也需要删除b，将a保留下来。之后
 *                  直接看出依次保留
 *                  由上述分析我们发现了元素操作的特点：先进后出
 *                      进栈 b c
 *                      出栈 c b 典型的栈数据结构的特点
 *              由此我们可以分析出此题可能会使用栈
 *
 *          2. "cbacdcbc"
 *              利用上述的分析的栈结构，模拟一下这个例子，看能否获取我们需要的结果，下面我们具体的模拟
 *              整个过程：
 *                  s = [] 初始栈
 *                  1. c进栈    s = [c]
 *                  2. b进栈    s = [c,b]
 *                  3. a进栈    s = [c,b,a]
 *                  4. c进栈    此时我们需要判断当前c，因为此时如果将c加入到栈中波坏了
 *                             栈的单调性，我们发现当前c的后面并没有a出现，但是c已经在栈中出现了
 *                  5.
 * 3. 代码实现
 *
 */

@SuppressWarnings("all")
public class 去除重复字母 {
    public static void main(String[] args) {

    }


    public static String removeDuplicateLetters(String s) {
        int len = s.length();
        char[] charArray = s.toCharArray();
        int[] lastIndex = new int[26]; // 记录字符数组中每个元素最后一次出现的位置
        for(int i = 0; i < len; i++) {
            lastIndex[charArray[i] - 'a'] = i;
        }
        boolean[] visited = new boolean[26]; // 记录字符是否在栈中的布尔数组
        for(int i = 0; i < len; i++) {
            visited[charArray[i] - 'a'] = false; // 初始化均没有出现在栈中
        }
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < len; i++) {
            // 判断当前元素是否在栈中
            if(visited[charArray[i]-'a'] == true) {
                continue;
            }
            // 判断当前字符与栈顶字符不满足字典序，并且栈顶元素在当前字符的后面出现，依次出栈
            while(!stack.empty() && charArray[i] < stack.peek() && lastIndex[stack.peek()-'a'] > i) {
                Character top = stack.pop();
                visited[top-'a'] = false;
            }
            stack.add(charArray[i]);
            visited[charArray[i]-'a'] = true;
        }
        StringBuilder ans = new StringBuilder();
        for(Character ch : stack) {
            ans.append(ch);
        }
        return ans.toString();
    }

}


